package com.wzp.server;

import java.util.Arrays;

/**
 * 删除数组重复项
 *
 * @author zhengpeng.wang
 */
public class ArrayRemoveDuplicates {

    public static void main(String[] args) {
        int[] ints = new int[]{1, 1, 2, 3, 3};
        int index = removeDuplicates2(ints);
        System.out.println(index);
    }

    public static int removeDuplicates2(int[] nums) {
//        if (nums.length == 0) {
//            return 0;
//        }
//        int index = 0;
//        for (int i = 0; i < nums.length; i++) {
//            if (nums[index] != nums[i]) {
//                index++;
//                nums[index] = nums[i];
//            }
//        }
//        return index + 1;

//        if (nums.length == 0) {
//            return 0;
//        }
//        int fast = 1, slow = 1;
//        while (fast < nums.length) {
//            if (nums[fast] != nums[slow]) {
//                slow++;
//                nums[slow] = nums[fast];
//            }
//            fast++;
//        }
//        return slow;

//        if (nums.length == 0) {
//            return 0;
//        }
//        int index = 0;
//        for (int i = 1; i < nums.length; i++) {
//            if (nums[index] != nums[i]) {
//                index++;
//                nums[index] = nums[i];
//            }
//        }
//        return index + 1;
        int fast = 1, slow = 0;
        while (fast < nums.length) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow + 1;

    }
















    /**
     * 一个有序数组 nums ，原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长
     * 度。
     * 不要使用额外的数组空间，必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
     * 双指针算法：
     * 数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要
     * nums[i]=nums[j]，我们就增加 j 以跳过重复项。
     * 当遇到 nums[j] ！= nums[i]时，跳过重复项的运行已经结束，必须把nums[j]）的值复制到 nums[i +
     * 1]。然后递增 i，接着将再次重复相同的过程，直到 j 到达数组的末尾为止。
     */
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }

    public static int removeDuplicates1(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int slow = 1, fast = 1;
        while (fast < nums.length) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }

    public static int mySqrt1(int x) {
        int low = 0, high = x, index = -1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if ((long) mid * mid < x) {
                index = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return index;
    }

    public static int mySqrt(int x) {
        int l = 0, r = x, index = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                index = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return index;
    }

    public static int mySqrt2(int x) {
        // 牛顿迭代 double res = (i + x / i) / 2;
        if (x == 0) {
            return 0;
        }
        return sqrts(x, x);
    }

    public static int sqrts(double i, int x) {
        double res = (i + x / i) / 2;
        if (res == i) {
            return (int) i;
        } else {
            return sqrts(res, x);
        }
    }


    public int maximumProduct(int[] nums) {
        // 最小的和第二小的
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        // 最大的、第二大的和第三大的
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        for (int x : nums) {
            if (x < min1) {
                min2 = min1;
                min1 = x;
            } else if (x < min2) {
                min2 = x;
            }

            if (x > max1) {
                max3 = max2;
                max2 = max1;
                max1 = x;
            } else if (x > max2) {
                max3 = max2;
                max2 = x;
            } else if (x > max3) {
                max3 = x;
            }
        }
        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }

//    public static void main(String[] args) {
//        System.out.println(removeDuplicates1(new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}));
//        System.out.println(mySqrt(8));
//        System.out.println(mySqrt2(8));
//        System.out.println(arrangeCoins(1804289383));
//        System.out.println(largestPerimeter(new int[]{3,2,3,4}));
//    }

    public static int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        for (int i = 2; i < nums.length; i++) {
            if (nums[i - 2] + nums[i - 1] > nums[i]) {
                return nums[i - 2] + nums[i - 1] + nums[i];
            }
        }
        return 0;
    }

//    public int minDepth(TreeNode root) {
        // if (root == null) {
        //     return 0;
        // }
        // if (root.left == null && root.right == null) {
        //     return 1;
        // }
        // int minDepth = Integer.MAX_VALUE;
        // if (root.left != null) {
        //     minDepth = Math.min(minDepth(root.left), minDepth);
        // }
        // if (root.right != null) {
        //     minDepth = Math.min(minDepth(root.right), minDepth);
        // }
        // return minDepth + 1;

//        if (root == null) {
//            return 0;
//        }
//        Queue<QueueNode> queue = new LinkedList<QueueNode>();
//        queue.offer(new QueueNode(root, 1));
//        while (!queue.isEmpty()) {
//            QueueNode nodeDepth = queue.poll();
//            TreeNode node = nodeDepth.node;
//            int depth = nodeDepth.depth;
//            if (node.left == null && node.right == null) {
//                return depth;
//            }
//            if (node.left != null) {
//                queue.offer(new QueueNode(node.left, depth + 1));
//            }
//            if (node.right != null) {
//                queue.offer(new QueueNode(node.right, depth + 1));
//            }
//        }
//        return 0;
//    }
//
//    class QueueNode {
//        TreeNode node;
//        int depth;
//
//        public QueueNode(TreeNode node, int depth) {
//            this.node = node;
//            this.depth = depth;
//        }
//    }
//
//    public double findMaxAverage(int[] nums, int k) {
//        int sum = 0;
//        for (int i = 0; i < k; i++) {
//            sum += nums[i];
//        }
//        int maxSum = sum;
//        for (int i = k; i < nums.length; i++) {
//            sum = sum + nums[i] - nums[i - k];
//            maxSum = Math.max(maxSum, sum);
//        }
//        return 1.0 * maxSum / k;
//    }
//
//
//    public void merge(int[] nums1, int m, int[] nums2, int n) {
//        int sum = Arrays.stream(nums1).sum();
//        int p1 = m - 1;
//        int p2 = n - 1;
//        int p = m + n - 1;
//        while ((p1 >= 0) && (p2 >= 0)) {
//            nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];
//        }
//        System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
//    }
//
//    public void merge(int[] nums1, int m, int[] nums2, int n) {
//        int[] nums1_copy = new int[m];
//        System.arraycopy(nums1, 0, nums1_copy, 0, m);//拷贝数组1
//        int p1 = 0;//指向数组1的拷贝
//        int p2 = 0;//指向数组2
//        int p = 0;//指向数组1
//
//        // 将数组1当成空数组，比较数组1的拷贝和数组2，将较小的放入空数组
//        while ((p1 < m) && (p2 < n)) {
//            nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];
//        }
//        //数组2和数组1不等长，将多出的元素拷贝
//        if (p1 < m) {
//            System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
//        }
//        if (p2 < n) {
//            System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
//        }
//    }
//
//    public void merge(int[] nums1, int m, int[] nums2, int n) {
//        System.arraycopy(nums2, 0, nums1, m, n);
//        Arrays.sort(nums1);
//    }
//
//
//    public static double sqrts1(double x, int n) {
//        double res = (x + (2 * n - x) / x) / 2;
//        if (res == x) {
//            return x;
//        } else {
//            return sqrts1(res, n);
//        }
//    }
//
//    public int arrangeCoins1(int n) {
//        return (int) sqrts1(n, n);
//    }
//
//    public static int arrangeCoins(int n) {
//        int low = 0, high = n;
//        while (low <= high) {
//            long mid = (high - low) / 2 + low;
//            long cost = (mid * (mid + 1)) / 2;
//            if (cost == n) {
//                return (int) mid;
//            } else if (cost < n) {
//                low = (int) (mid + 1);
//            } else {
//                high = (int) (mid - 1);
//            }
//        }
//        return high;
//    }

}
